#include <queue>
#include <ctime>
#include <chrono>
#include <string>
#include <cstring>
#include <iostream>
#include <stdexcept>
#include <algorithm>
#include <memory>

using namespace std;

struct SortBase
{
    // end contains no element

    virtual string whoami() = 0;
    virtual void sort(int *begin, int *end) = 0;

    void make_a_test(size_t n)
    {
        cout << "this is: " << whoami() << " test size " << n << endl;
        int *a = new int[n];
        generate_n(a, n, []()
                { return rand() - rand(); });
        unsigned long long s, t;
        s = chrono::steady_clock::now().time_since_epoch().count();
        try
        {
            this->sort(a, a + n);
            t = chrono::steady_clock::now().time_since_epoch().count();
            for (int i = 0; i < n - 1; i++)
                if (a[i] > a[i + 1])
                    throw logic_error("Sort Error!");
            cout << "Time spent: " << t - s << endl;
        }
        catch (runtime_error &e)
        {
            cout << e.what() << endl;
        }
        delete[] a;
    }
};

const int MAXN2 = 33333;

struct BubbleSort : SortBase
{
    void sort(int *begin, int *end)
    {
        if (end - begin > MAXN2)
            throw runtime_error("BubbleSort has taken weight out of it's range.");
        for (int *it1 = end; it1 != begin; it1--)
            for (int *it2 = begin + 1; it2 != it1; it2++)
                if (*(it2 - 1) > *it2)
                    swap(*(it2 - 1), *it2);
    }
    string whoami()
    {
        return "BubbleSort";
    }
};

struct InsertSort : SortBase
{
    void sort(int *begin, int *end)
    {
        if (end - begin > MAXN2)
            throw runtime_error("InsertSort has taken weight out of it's range.");
        for (int *it1 = begin; it1 != end; it1++)
        {
            int *pos = upper_bound(begin, it1, *it1);
            for (int *it2 = it1 - 1; it2 >= pos; it2--)
                swap(*(it2 + 1), *it2);
        }
    }
    string whoami()
    {
        return "InsertSort";
    }
};

struct ShellSort : SortBase
{
    void __sort(int *s, int n)
    {
        for (int g = n >> 1; g > 0; g >>= 1)
        {
            g |= 1;
            for (int i = g; i < n; i++)
            {
                int j = i;
                while (j >= g && s[j] < s[j - g])
                {
                    swap(s[j], s[j - g]);
                    j -= g;
                }
            }
        }
    }
    void sort(int *begin, int *end)
    {
        __sort(begin, end - begin);
    }
    string whoami()
    {
        return "ShellSort";
    }
};

struct RandomQuickSort : SortBase
{
    void __sort(int *a, int s, int t)
    {
        if (s == t)
            return;
        int i = s, j = t;
        int tmp, mid = a[rand() % (t - s) + s];
        while (i < j)
        {
            while (a[i] < mid)
                i++;
            while (mid < a[j])
                j--;
            if (i <= j)
            {
                tmp = a[i], a[i] = a[j], a[j] = tmp;
                i++, j--;
            }
        }
        if (s < j)
            __sort(a, s, j);
        if (i < t)
            __sort(a, i, t);
    }
    void sort(int *begin, int *end)
    {
        __sort(begin, 0, end - begin - 1);
    }
    string whoami()
    {
        return "RandomQuickSort";
    }
};

struct MergeSort : SortBase
{
    void __sort(int *a, int s, int t, int *c)
    {
        if (s == t)
            return;
        int mid = (s + t) >> 1;
        if (t - s >= 2)
        {
            __sort(a, s, mid, c);
            __sort(a, mid + 1, t, c);
        }
        int i = s, j = mid + 1, k = 0;
        while (i <= mid && j <= t)
        {
            if (a[i] <= a[j])
                c[k++] = a[i++];
            else
                c[k++] = a[j++];
        }
        while (i <= mid)
            c[k++] = a[i++];
        while (j <= t)
            c[k++] = a[j++];
        memcpy(a + s, c, sizeof(int) * (t - s + 1));
    }
    void sort(int *begin, int *end)
    {
        int *c = new int[end - begin];
        __sort(begin, 0, end - begin - 1, c);
        delete[] c;
    }
    string whoami()
    {
        return "MergeSort";
    }
};

struct BinaryHeapSort : SortBase
{
    void Insert(int *heap, int &tot, int tar)
    {
        int cur, fa;
        heap[++tot] = tar;
        cur = tot;
        while (cur > 1)
        {
            fa = cur >> 1;
            if (heap[cur] >= heap[fa])
                break;
            swap(heap[cur], heap[fa]);
            cur = fa;
        }
    }
    void Delete(int *heap, int &tot)
    {
        int cur, son;
        swap(heap[1], heap[tot--]);
        cur = 1;
        while ((son = cur << 1) <= tot)
        {
            son ^= son < tot && heap[son ^ 1] < heap[son];
            if (heap[cur] <= heap[son])
                break;
            swap(heap[cur], heap[son]);
            cur = son;
        }
    }
    void sort(int *begin, int *end)
    {
        int tot = 0;
        int *heap = new int[end - begin + 1];
        for (int *it = begin; it != end; it++)
            Insert(heap, tot, *it);
        for (int *it = begin; it != end; it++)
            Delete(heap, tot);
        reverse_copy(heap + 1, heap + (end - begin) + 1, begin);
        delete[] heap;
    }
    string whoami()
    {
        return "BinaryHeapSort";
    }
};

struct RadixSort : SortBase
{
    void __sort(const int n, unsigned *a, unsigned *b)
    {
        unsigned r1[0x100], r2[0x100], r3[0x100], r4[0x100];
        memset(r1, 0, sizeof(r1)), memset(r2, 0, sizeof(r2));
        memset(r3, 0, sizeof(r3)), memset(r4, 0, sizeof(r4));

        register unsigned i, tmp_int;
        register unsigned *j, *tar;

        for (j = a, tar = a + n; j != tar; ++j)
        {
            tmp_int = *j;
            ++r1[tmp_int & 0xff];
            ++r2[(tmp_int >> 0x8) & 0xff];
            ++r3[(tmp_int >> 0x10) & 0xff];
            ++r4[tmp_int >> 0x18];
        }
        for (i = 1; i <= 0xff; ++i)
        {
            r1[i] += r1[i - 1];
            r2[i] += r2[i - 1];
            r3[i] += r3[i - 1];
            r4[i] += r4[i - 1];
        }
        for (j = a + n - 1; j != a - 1; --j)
            b[--r1[(*j) & 0xff]] = *j;
        for (j = b + n - 1; j != b - 1; --j)
            a[--r2[((*j) >> 0x8) & 0xff]] = *j;
        for (j = a + n - 1; j != a - 1; --j)
            b[--r3[((*j) >> 0x10) & 0xff]] = *j;
        for (j = b + n - 1; j != b - 1; --j)
            a[--r4[(*j) >> 0x18]] = *j;
    }
    void sort(int *begin, int *end)
    {
        int *b = new int[end - begin];
        __sort(end - begin, reinterpret_cast<unsigned *>(begin), reinterpret_cast<unsigned *>(b));
        reverse(begin, end);
        reverse(begin, lower_bound(begin, end, 0));
        reverse(upper_bound(begin, end, 0), end);
        delete[] b;
    }
    string whoami()
    {
        return "RadixSort";
    }
};

struct STDQuickSort : SortBase
{
    void sort(int *begin, int *end)
    {
        std::sort(begin, end);
    }
    string whoami()
    {
        return "STDQuickSort";
    }
};

struct STDMergeSort : SortBase
{
    void sort(int *begin, int *end)
    {
        std::stable_sort(begin, end);
    }
    string whoami()
    {
        return "STDMergeSort";
    }
};

struct STDPriorityQueueSort : SortBase
{
    void sort(int *begin, int *end)
    {
        priority_queue<int, vector<int>, greater<int>> pq;
        for (int *it = begin; it != end; it++)
            pq.push(*it);
        for (int *it = begin; it != end; it++)
            *it = pq.top(), pq.pop();
    }
    string whoami()
    {
        return "STDPriorityQueueSort";
    }
};

class Context
{
    shared_ptr<SortBase> sortbase;

public:
    Context(shared_ptr<SortBase> sb) : sortbase(sb) {}
    void executeSort(int *begin, int *end)
    {
        cout << sortbase->whoami() << ":" << endl;
        sortbase->sort(begin, end);
    }
};

int main()
{
    // srand(19491001);
    int a[10] = {23, 42, 3, 23, 4, 5, 67, 10, 13, 15};
    shared_ptr<SortBase> stbs(new BubbleSort);
    Context context(stbs);
    context.executeSort(a, a + 10);
    for (int i = 0; i < 10; i++)
    {
        printf("%d%c", a[i], " \n"[i == 9]);
    }
    return 0;
}